package com.leetcode;

/**
 * 730. 统计不同回文子序列
 * <p>
 * 给定一个字符串 s，返回 s 中不同的非空「回文子序列」个数 。
 * 通过从 s 中删除 0 个或多个字符来获得子序列。
 * 如果一个字符序列与它反转后的字符序列一致，那么它是「回文字符序列」。
 * 如果有某个 i , 满足 ai != bi ，则两个序列 a1, a2, ... 和 b1, b2, ... 不同。
 * <p>
 * 注意：
 * 结果可能很大，你需要对 109 + 7 取模 。
 * <p>
 * 提示：
 * 1 <= s.length <= 1000
 * s[i] 仅包含 'a', 'b', 'c' 或 'd'
 */
public class LeetCode730 {

    public static void main(String[] arg0) {

    }

    public static int countPalindromicSubsequences(String s) {
        int res = 0;

        final int MOD = 1000000007;
        int length = s.length();
        int[][][] dp = new int[4][length][length];
        for (int i = 0; i < length; i++) {
            dp[s.charAt(i) - 'a'][i][i] = 1;
        }

        for (int len = 2; len <= length; len++) {
            for (int i = 0; i + len <= length; i++) {
                int j = i + len - 1; // 当前循环的「回文字符序列」长度，对应在dp中的下标，所以有减1
                for (char c = 'a'; c <= 'd'; c++) {
                    int k = c - 'a';
                    if (s.charAt(i) == c && s.charAt(j) == c) {
                        dp[k][i][j] = (2 + (dp[0][i + 1][j - 1] + dp[1][i + 1][j - 1]) % MOD + (dp[2][i + 1][j - 1] + dp[3][i + 1][j - 1]) % MOD) % MOD;
                    } else if (s.charAt(i) == c) {
                        dp[k][i][j] = dp[k][i][j - 1];
                    } else if (s.charAt(j) == c) {
                        dp[k][i][j] = dp[k][i + 1][j];
                    } else {
                        dp[k][i][j] = dp[k][i + 1][j - 1];
                    }
                }
            }
        }

        // 动态规划只用到了二维数组的右上角部分，所以最后的结果会归结到四个二维数组的 [0][length - 1] 上
        // 并且每次规划都逐渐影响向右上角45度倾斜向下的那一行
        for (int i = 0; i < 4; i++) {
            res = (res + dp[i][0][length - 1]) % MOD;
        }

        return res;
    }

}
